package com.sedric.sort;

public class HeapSort {

	public static Integer[] maxHeapSort(Integer[] arr) {
		for(int i = 0; i < arr.length; i++) {
			buildMaxHeapTree(arr, arr.length - 1 - i);
			CommonUtils.swap(arr, 0, arr.length - 1 - i);
		}
		return arr;
	}

	private static void buildMaxHeapTree(Integer[] arr, int lastIndex) {
		for(int i = (lastIndex - 1) / 2; i >= 0; i--) {
			int parent = i;
			int leftChild = parent * 2 + 1;
			if (2 * parent + 1 <= lastIndex) {
				int biggerChild = arr[leftChild];
				if (leftChild < lastIndex && arr[leftChild] < arr[leftChild + 1]) {
					biggerChild = arr[leftChild + 1];
				}
				if (arr[parent] < arr[biggerChild]) {
					CommonUtils.swap(arr, parent, biggerChild);
				}
			}
		}
	}

	public static Integer[] minHeapSort(Integer[] arr) {
		// buildMinHeapTree(arr, lastIndex)
		return arr;
	}

	private static void buildMinHeapTree(Integer[] arr, int lastIndex) {

	}

	public static void main(String[] args) {
		Integer[] arr = CommonUtils.generatorRandomIntegerArray(10);

		CommonUtils.printArray(arr);
		maxHeapSort(arr);
		CommonUtils.printArray(arr);
	}
}